#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/8/24 10:05
# ===========================================
#       题目名称： 33. 搜索旋转排序数组
#       题目地址： https://leetcode.cn/problems/search-in-rotated-sorted-array/
#       题目描述： https://note.youdao.com/s/RRXNSXjR
# ===========================================


class Solution:
    """
        实现思路：
            二分查找
        要求：
            设计一个时间复杂度为 O(log n) 的算法解决此问题。
    """

    def search(self, nums, target):
        if not nums:
            return -1
        if len(nums) == 1:
            if nums[-1] == target:
                return 0
            else:
                return -1
        left, right = 0, len(nums) - 1
        while left <= right:
            if nums[right] < target:
                if nums[left] == target:
                    return left
                elif nums[left] > target:
                    break
                else:
                    left += 1
            else:
                if nums[right] == target:
                    return right
                else:
                    right -= 1
        return -1


if __name__ == '__main__':
    s = Solution()
    # 4
    print(s.search(nums=[4, 5, 6, 7, 0, 1, 2], target=0))
    # -1
    print(s.search(nums=[4, 5, 6, 7, 0, 1, 2], target=3))
    # -1
    print(s.search(nums=[1, ], target=0))
    # 1
    print(s.search(nums=[1, 3, 5], target=3))
    # 1
    print(s.search(nums=[3, 5, 1], target=5))
